package week01

import "math"

// 84. 柱状图中最大的矩形
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

// 单调递增

func largestRectangleArea(heights []int) int {
	// 前面不影响后面，前面的可以单独计算
	// 单调递增栈
	var stack []Rect
	heights = append(heights, 0) // 用于最后清空栈元素
	var area int
	for _, h := range heights {
		var accWidth = 0
		for len(stack) > 0 && stack[len(stack)-1].Height > h {
			var top = stack[len(stack)-1]
			accWidth += top.Width
			// 计算面积
			area = max(accWidth * top.Height, area)
			// 出栈
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, Rect{h, accWidth+1})
	}
	return area
}

type Rect struct {
	Height int
	Width int
}

func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}